package experiment4.knapsack;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class BABMethodKnapsack {
    ArrayList<Goods> goodsArrayList = null;
    boolean[] resultVec;
    Node resultChild = null;
    ArrayList<Node> compareList = null;
    int currentBestValue = 0;


    class Node  {

        int index;
        boolean load;
        Node parent;
        int currentValue;
        int capacity;
        float estimatedValue;

        Node() {}

        Node(int index, boolean load, int currentValue, int capacity, float estimatedValue, Node parent) {
            this.index = index;
            this.load = load;
            this.currentValue = currentValue;
            this.capacity = capacity;
            this.estimatedValue = estimatedValue;
            this.parent = parent;
        }


    }

    public int solution(ArrayList<Goods> goodsArrayList, int capacity) {
        this.goodsArrayList = new ArrayList<>();
        for (int i = 0;i < goodsArrayList.size();i++){
            this.goodsArrayList.add(goodsArrayList.get(i));
        }
        PriorityQueue<Node> priorityQueue = new PriorityQueue(new Comparator<Node>() {

            @Override
            public int compare(Node o1, Node o2) {
                return Float.compare(o2.estimatedValue,o1.estimatedValue);
            }
        });
        resultVec = new boolean[goodsArrayList.size()];
        compareList = new ArrayList<Node>();
        Node root = new Node(-1, false, 0, capacity, 0f, null);

        priorityQueue.add(root);
        Node parent = null;

        while (!priorityQueue.isEmpty()) {
            parent = priorityQueue.poll();

            if (parent.index + 1 == goodsArrayList.size()){
                if ( Float.compare(parent.estimatedValue, priorityQueue.peek().estimatedValue) >= 0){
                    break;
                }
                priorityQueue.add(parent);
                continue;
            }

            Goods goods = goodsArrayList.get(parent.index + 1);
            //装入第i个物品
            if (parent.capacity >= goods.weight) {

                float estimatedValue = parent.currentValue + bound(parent.index + 1,parent.capacity);

                Node leftChild = new Node(parent.index + 1,
                        true,
                        parent.currentValue + goods.value,
                        parent.capacity - goods.weight,
                        estimatedValue,
                        parent);
                if (parent.currentValue + goods.value > currentBestValue){

                    currentBestValue = parent.currentValue + goods.value;
                }
                priorityQueue.add(leftChild);
            }
            //不装入第i个物品
            float estimatedValue = parent.currentValue + bound(parent.index + 2,parent.capacity);
            if (estimatedValue >= currentBestValue)
            {
                Node rightChild = new Node(parent.index + 1,
                        false,
                        parent.currentValue,
                        parent.capacity,
                        estimatedValue,
                        parent);

                priorityQueue.add(rightChild);
            }

        }
        resultChild = parent;
        return currentBestValue;
    }
    public boolean[] solutionVector() {

        Node parent = resultChild;
        while(parent.index != -1){
            resultVec[parent.index] = parent.load;
            parent = parent.parent;
        }
        return resultVec;
    }
    private float bound(int i,int capacity) {
        float maxValue = 0f;
        for (; i < goodsArrayList.size(); i++) {
            Goods goods = goodsArrayList.get(i);
            if (capacity >= goods.weight) {
                maxValue += goods.value;
                capacity -= goods.weight;
            } else {
                maxValue += (capacity * goods.weightValue);
            }
        }
        return maxValue;
    }
}
